package com.fosss.test.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 图
 */
public class GraphDemo {
    public static void main(String[] args) {
//        String[] arr={"A","B","C","D","E"};
//        Graph graph = new Graph(5, arr);
//        graph.setMatrix(0,1);//A-B
//        graph.setMatrix(0,2);//A-C
//        graph.setMatrix(1,2);//B-C
//        graph.setMatrix(1,3);//B-D
//        graph.setMatrix(1,4);//B-D

        String[] arr={"1","2","3","4","5","6","7","8"};
        Graph graph = new Graph(8, arr);
        graph.setMatrix(0,1);
        graph.setMatrix(0,2);
        graph.setMatrix(1,3);
        graph.setMatrix(1,4);
        graph.setMatrix(3,7);
        graph.setMatrix(4,7);
        graph.setMatrix(2,5);
        graph.setMatrix(2,6);
        graph.setMatrix(5,6);

        System.out.println("=======================邻接矩阵================");
        graph.showMatrix();

//        System.out.println("=======================深度遍历================");
//        graph.dfs();

        System.out.println("=======================广度遍历================");
        graph.bfs();
    }
}
class Graph{
    //顶点数组
    String[] vertexes;
    //邻接矩阵
    int[][] matrix;
    //创建一个数组，记录各个顶点是否被访问过
    boolean[] isVisited;

    /**
     * @param n 顶点的个数
     */
    public Graph(int n,String[] arr) {
        this.vertexes =arr ;
        this.matrix=new int[n][n];
        this.isVisited=new boolean[n];
    }

    /**
     * 设置邻接矩阵，即顶点之间的关系，0表示不相连，1表示相连
     */
    public void setMatrix(int v1,int v2){
        matrix[v1][v2]=1;
        matrix[v2][v1]=1;
    }

    /**
     * 打印邻接矩阵
     */
    public void showMatrix(){
        for (int[] ints : matrix) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * 深度优先遍历
     */
    public void dfs(){
        for(int i=0;i<vertexes.length; i++){//挨个遍历，分别处理
            if(!isVisited[i]){
                dfsImpl(i);
            }
        }
    }
    /**
     * 深度遍历中用于递归的方法
     * @param n 表示顶点数组中第几个要被处理的数
     */

    private void dfsImpl(int n) {
        System.out.print(vertexes[n]+" ");
        isVisited[n]=true;//设置为已访问
        //查找与n相连的顶点的下标
        for (int i = 0; i < matrix[n].length; i++) {
            if(matrix[n][i]==1&&!isVisited[i]){
                //说明是相连的且没有被访问过
                //对这个顶点进行深度遍历
                dfsImpl(i);
            }
        }
    }

    /**
     * 广度优先遍历
     */
    public void bfs(){
        for(int i=0;i<vertexes.length; i++){//挨个遍历，分别处理
            if(!isVisited[i]){
                bfsImpl(i);
            }
        }
    }

    /**
     * 广度优先遍历中的方法
     * @param n 表示顶点数组中第几个要被处理的数
     */

    private void bfsImpl(int n) {
        //用linkedList模拟队列（先进先出）
        LinkedList<Integer> queue=new LinkedList<>();
        //加入队列
        queue.add(n);
        System.out.print(vertexes[n]+" ");
        isVisited[n]=true;//设置为已访问

        while (queue.size()>0){//队列中不为空
            //弹出一个值
             n= queue.pop();
            //查找与n相连的顶点的下标
            for (int i = 0; i < matrix[n].length; i++) {
                if(matrix[n][i]==1&&!isVisited[i]){
                    //说明是相连的且没有被访问过
                    //设置为已访问
                    isVisited[i]=true;
                    System.out.print(vertexes[i]+" ");
                    //加入队列
                    queue.add(i);
                }
            }
        }

    }
}
























